#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <error.h>

typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
} bitree_t;

//根节点从1开始
// n 表示一共的节点数
bitree_t *create_bitree(int i, int n)
{
    bitree_t *r = malloc(sizeof(bitree_t));
    r->data = i;
    printf("i=%d\n", i);

    if (2 * i <= n) //有左孩子
    {
        r->lchild = create_bitree(2 * i, n);
    }
    else
    {
        r->lchild = NULL; //左孩子为空
    }

    if (2 * i + 1 <= n)
    {
        r->rchild = create_bitree(2 * i + 1, n);
    }
    else
    {
        r->rchild = NULL; //右孩子为空
    }

    return r;
}

//递归一定要有结束条件
int preorder(bitree_t *b) /*根 左 右*/
{
    //结束条件
    if (b == NULL)
    {
        return 0;
    }
    //先访问根
    printf("%d ", b->data);

    //在访问左
    preorder(b->lchild);

    //最后访问右
    preorder(b->rchild);

    return 0;
}

int inorder(bitree_t *b) /*左 根 右*/
{
    //结束条件
    if (b == NULL)
    {
        return 0;
    }
    //先访问左
    inorder(b->lchild);

    //在访问根
    printf("%d ", b->data);

    //最后访问右
    inorder(b->rchild);

    return 0;
}

int postorder(bitree_t *b) /*左 右 根*/
{
    //结束条件
    if (b == NULL)
    {
        return 0;
    }

    //先访问左
    postorder(b->lchild);

    //在访问右
    postorder(b->rchild);

    //最后访问根
    printf("%d ", b->data);

    return 0;
}

int main(int argc, char const *argv[])
{
    bitree_t *R = create_bitree(1, 15);
    printf("先序顺序:");
    preorder(R);
    printf("\n");

    printf("中序顺序:");
    inorder(R);
    printf("\n");

    printf("后序顺序:");
    postorder(R);
    printf("\n");

    return 0;
}
